package com;

/**
 * @Author wy
 * @Description TODO
 * @Date 2023/12/6 14:16
 * @Version 1.0
 */
public class hxzyQuickSort {

    public static void main(String[] args) {
        int[] nums={10,2,0,1,8,3};
        quickSort(nums);
        for(int s :nums){
            System.out.print(s+"\t");
        }
    }
    public static void quickSort(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
    }

    public static void quickSort(int[] nums, int start, int end) {
        if (start < end) {
            // 划分，把数组分为两部分。
            int j = partition2(nums, start, end);
            quickSort(nums, start, j - 1);// 递归左边部分。
            quickSort(nums, j + 1, end);  // 递归右边部分。
        }
    }

    // 这个是快排的重点，使用数组中的第一个元素作为中枢值，把数组分为两部分。
    private static int partition(int[] nums, int start, int end) {
        // 默认数组的第一个元素作为中枢值。
        int pivotValue = nums[start];
        int j = start;// 使用 i ，j 两个指针。
        for (int i = start + 1; i <= end; i++) {
            // 当前元素始终和中枢值进行比较，如果小于中枢值就往前挪。
            if (nums[i] < pivotValue)
                swap(nums, ++j, i); // 交换之前，j 需要先往后挪一步。
        }

        swap(nums, j, start);// 交换位置。
        return j;// 返回中枢值的下标。
    }

    private static int partition2(int[] nums, int start, int end) {
        // 默认数组的第一个元素作为中枢值。
        int pivotValue = nums[start];
        while (start < end) {
            // 从后往前查找小于中枢值的元素。
            while (start < end && nums[end] >= pivotValue) {
                --end;
            }
            swap(nums, start, end);// 将这个小的元素和中枢值。

            // 从前往后查找大于中枢值的元素。
            while (start < end && nums[start] <= pivotValue) {
                ++start;
            }
            swap(nums, start, end);// 将这个大的元素和中枢值。
        }
        return start;// 返回中枢值所在的位置。
    }



    private static void swap(int[] nums, int j, int start) {
        int temp=nums[j];
        nums[j]=nums[start];
        nums[start]=temp;
    }


}
